1. Statement of the Technical Field
The inventive arrangements relate to communications systems. More particularly, the inventive arrangements relate to a method and apparatus for generating an arbitrary permutation ordering of numbers and its application in a variety of communication system structures, including random number generators.
2. Description of the Related Art
Many systems requiring random sequences typically include ring generators and/or other cyclic structures. A ring generator is a simple structure over a finite field that exhaustively produces possible outputs through repeated mapping. The mapping is some combination of an additive and a multiplicative mapping, with irreducible polynomials being ideal. For example, a ring generator includes repeated computations of an irreducible polynomial f(x)=3x3+3x2+x on a finite Galois field GF[11]. A main limitation of a ring generator is that its orbits are highly deterministic. As such, knowledge of a mapping and current finite field conditions gives complete knowledge of an output sequence.
In systems requiring random sequences, ring generators are often employed in algorithms for modifying a sequence of data bits. Such algorithms typically include arithmetic operations to be performed in a finite or Galois field. A finite or Galois field GF[p] is a field that contains only finitely many elements, namely {0, 1, 2, . . . , p-1}. As such, all arithmetic operations performed in the finite or Galois field result in an element within that field. The finite or Galois field GF[p] has a finite field size defined by the Galois characteristic p. As such, an output sequence created through repeated mapping repeats every pth element. This repetitive behavior produces correlations thereby making the decoding of an output sequence relatively easy when p is small. Consequently, the algorithms also typically include operations for expanding the finite or Galois field size so that the period of repetition is increased.
There are many methods known in the art for expanding a finite or Galois field GF[p] where p is an integer power of two (2), 2k. The simplest such method for expanding a finite or Galois field GF[2k] includes increasing a number of input bits. Other methods include coupling the ring generator to other generators. For example, the ring generator may be coupled to an arbitrary number of other generators (assumed to have a mutually prime characteristic) comprised of digital hardware implementing the Chinese Remainder Theorem (CRT). As should be understood, CRT computations are performed to combine mixed-radix computations. CRT computations may only be used if inputs to the generator are mutually prime numbers. Despite the advantages of this method, it suffers from certain drawbacks. For example, this method is cyclic and fixed by nature. CRT computations of elements in odd prime number bases with digital hardware are computationally inefficient. Also, an output sequence of the generator is highly deterministic if the mutually prime numbers are known a priori.
These systems requiring random sequences also typically rely on deterministic scrambling methods to help mask an output sequence so that an outside observer is unable to determine the output sequence. Scrambling methods are used to increase the entropy of an output relative to any given sequence of inputs. As such, these systems include scramblers. A scrambler operates according to a deterministic scrambling algorithm so that the original signal can be recovered from a scrambled signal. Deterministic scrambling methods and associated algorithms are well known to persons skilled in the art, and therefore will not be described in detail herein.
However, it should be understood that one such deterministic scrambling method includes implementing a deterministic scrambling algorithm that uses substitution box (S-box) functions to scramble data. An S-box is an array of numbers used to add additional variance into an output sequence of a system in order to protect the output sequence from reverse engineering. An S-box function often has a number of desired properties. For example, a deterministic scrambling algorithm uses an S-box, but a deterministic descrambling algorithm uses an inverse of the S-box. As such, the S-box function is invertible so that an output sequence can be obtained from a scrambled sequence. This deterministic scrambling method also includes creating complex mixing networks, such as a Feistel structure. As should be understood, a Feistel structure combines multiple rounds of repeated operations. Such operations include, but are not limited to, bit-shuffling, nonlinear functions, and linear functions. Despite the advantages of this deterministic scrambling method, it suffers from certain drawbacks. For example, this deterministic scrambling method is time-invariant. This deterministic scrambling method can also be resource intensive.
In view of the forgoing, there remains a need for a method for expanding a finite or Galois field size that is more computationally efficient than conventional finite held expansion methods. There is also a need for an invertible method for increasing the entropy of an output sequence that is more computationally efficient than conventional deterministic scrambling methods. Such methods also need to be designed for providing a high degree of security feature to a system. Most significantly, there is further a need for a method and apparatus for generating an arbitrary permutation ordering of numbers that can be used in a variety of communication system applications.